package com.linyaonan.leetcode.medium._3325;

import java.util.HashMap;
import java.util.Map;

/**
 * 给你一个字符串 s 和一个整数 k，在 s 的所有子字符串中，请你统计并返回 至少有一个 字符 至少出现 k 次的子字符串总数。
 *
 * 子字符串 是字符串中的一个连续、 非空 的字符序列。
 *
 *
 *
 * 示例 1：
 *
 * 输入： s = "abacb", k = 2
 *
 * 输出： 4
 *
 * 解释：
 *
 * 符合条件的子字符串如下：
 *
 * "aba"（字符 'a' 出现 2 次）。
 * "abac"（字符 'a' 出现 2 次）。
 * "abacb"（字符 'a' 出现 2 次）。
 * "bacb"（字符 'b' 出现 2 次）。
 * 示例 2：
 *
 * 输入： s = "abcde", k = 1
 *
 * 输出： 15
 *
 * 解释：
 *
 * 所有子字符串都有效，因为每个字符至少出现一次。
 *
 *
 *
 * 提示：
 *
 * 1 <= s.length <= 3000
 * 1 <= k <= s.length
 * s 仅由小写英文字母组成。
 *
 * @author: Lin
 * @date: 2024/10/31
 */
public class CountSubstringsWithKFrequencyCharactersI {

    /**
     * 滑动窗口
     * @param s
     * @param k
     * @return
     */
    public int numberOfSubstrings(String s, int k) {
        int l = 0;
        int r = 0;

        int[] saved = new int[26];
        int count = 0;
        while (l <= r && r < s.length()) {
            char current = s.charAt(r);
            saved[current - 'a']++;

            while (checkHasOverK(saved, k)) {
                count += (s.length() - r);
                saved[s.charAt(l) - 'a']--;
                l++;
            }

            r++;
        }

        return count;
    }

    private boolean checkHasOverK(int[] org, int k) {
        for (int i : org) {
            if (i >= k) {
                return true;
            }
        }

        return false;
    }

}
